package written.test;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/28  19:35
 * @Description:
 */
class Main4 {
    public static void main(String[] args) {
        // obstacleGrid中1代表的是该位置有障碍物，从0开始
//        int[][] obstacleGrid = {{0,0,0},{0,0,0},{0,0,0}};
//        System.out.println(uniquePathsWithObstacles(obstacleGrid));
    }





    public static  int  uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][] dp= new int[m][n];// dp（i，j） 表示到达i,j  的总种树
        for(int i=0;i<m;++i){
            if(obstacleGrid[i][0]==0) dp[i][0]=1;
            else break;
        }
        for(int i=0;i<n;++i){
            if(obstacleGrid[0][i]==0){   // 不是障碍物
                dp[0][i]=1;
            }else break;
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                if(obstacleGrid[i][j]==0){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
                else dp[i][j]=0;
            }
        }
        return dp[m-1][n-1];
    }

};

